package cn.mayday.algorithms.year2021.month1.C双指针专题;

/**
 * 翻转单词顺序
 * 示例 1：
 * <p>
 * 输入: "the sky is blue"
 * 输出: "blue is sky the"
 *
 * @author: mayday
 * @date: 2021/5/11 22:41
 * @version: 1.0
 */
public class Offer058IReverseWords {

    public static void main(String[] args) {
        String input = " hello world! ";
        String result1 = new Offer058IReverseWords().reverseWords(input);
        System.out.println("result1 ===" + result1);
    }

    // 方法一： 循环遍历，时间复杂度N，空间复杂度，因为借助了数组，也在N
    public String reverseWords1(String s) {
        String[] temp = new String[s.length()];
        int count = 0;
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            // 如果不为空时，拼接。如果是最后一个元素，添加进去
            if (s.charAt(i) != ' ') {
                builder.append(s.charAt(i));
                if (i == s.length() - 1) {
                    temp[count++] = builder.toString();
                    builder = new StringBuilder(); // 重置
                }
            } else if (builder.length() != 0) { // 如果为空格时，且前面已经凭借的内容不为空，添加进去，并重置
                temp[count++] = builder.toString();
                builder = new StringBuilder(); // 重置
            }
        }

        StringBuilder result = new StringBuilder();
        for (int index = count - 1; index >= 0; index--) {
            result.append(temp[index]);
            if (index != 0) {
                result.append(' ');
            }
        }
        return result.toString();
    }

    /**
     * 方法二：双指针：用于记录边界
     * 算法解析：
     * 倒序遍历字符串 s，记录单词左右索引边界 i , j ；
     * 每确定一个单词的边界，则将其添加至单词列表 res ；
     * 最终，将单词列表拼接为字符串，并返回即可。
     * <p>
     * 复杂度分析：
     * 时间复杂度 O(N) ： 其中 N 为字符串 s 的长度，线性遍历字符串。
     * 空间复杂度 O(N)： 新建的 list(Python) 或 StringBuilder(Java) 中的字符串总长度 ≤N ，占用 O(N)大小的额外空间。
     */


    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();

        while (i >= 0) {
            while (i >= 0 && s.charAt(i) != ' ') { // 左边界一直不是空串时，一直减
                i--;
            } // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词

            while (i >= 0 && s.charAt(i) == ' ') { // 如果指定是空格，跳过空格
                i--;
            } // 跳过单词间空格

            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }
}
